package leetcode;

import java.util.Arrays;

/**
 * 698. 划分为k个相等的子集      https://leetcode.cn/problems/partition-to-k-equal-sum-subsets
 */
public class LeetCode698 {

    public static boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) {
            return false;
        }
        int per = sum / k;
        if (nums[nums.length - 1] > per) {
            return false;
        }
        // 分成k个桶
        int[] bucket = new int[k];
        Arrays.fill(bucket, per);
        // 排序
        Arrays.sort(nums);
        return dfs(nums, nums.length - 1, bucket, k);
    }

    public static boolean dfs(int[] nums, int cur, int[] bucket, int k) {
        if (cur < 0) {
            return true;
        }
        // 每个桶遍历
        for (int i = 0; i < k; i++) {
            // 优化
            if (i > 0 && bucket[i - 1] == bucket[i]) {
                continue;
            }
            if (nums[cur] == bucket[i] || bucket[i] - nums[cur] >= nums[0]) {
                bucket[i] -= nums[cur];
                if(dfs(nums, cur - 1, bucket, k)) {
                    return true;
                }
                bucket[i] += nums[cur];
            }
        }
        return false;
    }
}
